#include <bits/stdc++.h>
using namespace std;
#define int long long
long long a[200005],seg[200005<<2],lsh[200005],tag[200005<<2];
void build(int u,int l,int r){
    tag[u]=0;
    if(l==r){
        seg[u]=(l==0?0:-1e18);
        return ;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    seg[u]=max(seg[u<<1],seg[u<<1|1]);
}
void put_lazy(int u,int val){
    seg[u]+=val;
    tag[u]+=val;
}
void push_down(int u){
    put_lazy(u<<1,tag[u]);
    put_lazy(u<<1|1,tag[u]);
    tag[u]=0;
}
int query(int u,int l,int r,int pos){
    if(l==r){
        return seg[u];
    }
    push_down(u);
    int mid=l+r>>1;
    if(pos<=mid)return query(u<<1,l,mid,pos);
    else return query(u<<1|1,mid+1,r,pos);
}
void ckval(int u,int l,int r,int pos,int val){
    if(l==r){
        seg[u]=max(seg[u],val);
        return ;
    }
    int mid=l+r>>1;
    push_down(u);
    if(pos<=mid)ckval(u<<1,l,mid,pos,val);
    else ckval(u<<1|1,mid+1,r,pos,val);
    seg[u]=max(seg[u<<1],seg[u<<1|1]);
}
signed main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            lsh[i]=a[i];
        }
        sort(lsh+1,lsh+n+1);
        int tot=unique(lsh+1,lsh+n+1)-lsh-1;
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(lsh+1,lsh+tot+1,a[i])-lsh;
        }
        build(1,0,tot);
        for(int i=2;i<=n;i++){
            int num=max(seg[1],lsh[a[i]]+query(1,0,tot,a[i]));
            put_lazy(1,(a[i]==a[i-1]?lsh[a[i]]:0));
            ckval(1,0,tot,a[i-1],num);
        }
        cout<<seg[1]<<'\n';
    }
}